package primary.tree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author Elephas
 * @Date 2022/1/8
 **/
public class IsValidBST {
    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTreeNode(new Integer[]{5,1,4,null,null,3,6});
        isValidBST(root);
        return;
    }

    /*
        解法一：BST中root的值必定大于左边的最大值，小于右子树的最小值，且左子树右子树均满足该性质
     */
    public static boolean isValidBST(TreeNode root){
        if(root == null){
            return true;
        }
        boolean cond1 = true,cond2 = true;
        int left,right;
        if(root.left != null && root.right != null){
            left = maxTreeValue(root.left);
            right = minTreeValue(root.right);
            cond1 = root.val > left && root.val < right;
            cond2 = isValidBST(root.left) && isValidBST(root.right);
        }else if(root.left != null){
            left = maxTreeValue(root.left);
            cond1 = left < root.val ? true:false;
            cond2 = isValidBST(root.left);
        }else if(root.right != null){
            right = minTreeValue(root.right);
            cond1 = right > root.val ? true:false;
            cond2 = isValidBST(root.right);
        }
        return cond1 && cond2;
    }
    public static int maxTreeValue(TreeNode root){
        int left,right;
        if(root.left!=null && root.right != null){
            left = maxTreeValue(root.left);
            right = maxTreeValue(root.right);
            if(left>right){
                return Math.max(left, root.val);
            }else{
                return Math.max(right, root.val);
            }
        }else if(root.left != null){
            left = maxTreeValue(root.left);
            return Math.max(left, root.val);
        }else if(root.right != null){
            right = maxTreeValue(root.right);
            return Math.max(right, root.val);
        }else {
            return root.val;
        }
    }
    public static int minTreeValue(TreeNode root){
        int left,right;
        if(root.left!=null && root.right != null){
            left = minTreeValue(root.left);
            right = minTreeValue(root.right);
            if(left<right){
                return Math.min(left, root.val);
            }else{
                return Math.min(right, root.val);
            }
        }else if(root.left != null){
            left = minTreeValue(root.left);
            return Math.min(left, root.val);
        }else if(root.right != null){
            right = minTreeValue(root.right);
            return Math.min(right, root.val);
        }else {
            return root.val;
        }
    }

    /*
        解法二： BST的中序遍历是递增的，由此判定一棵树是否是BST,通过栈实现
     */
    public boolean isValidBST2(TreeNode root){
        if(root == null)
            return true;
        Deque<TreeNode> deque = new ArrayDeque<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.empty() && root!= null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            deque.add(root);
            root = root.right;
        }
        return true;
    }

}
